#include "merge_sort.h"
#include "common/common.h"
#include "common/array.h"

static void merge(int array[], int mid, int size) {
  int *sub_array1, *sub_array2;
  int i, j, m;

  sub_array1 = (int*)malloc(mid * sizeof(int));
  sub_array2 = (int*)malloc((size - mid) * sizeof(int));
  for (i = 0; i < mid; ++i) {
    sub_array1[i] = array[i];
  }
  for (j = 0; i < size; ++j, ++i) {
    sub_array2[j] = array[i];
  }
  for (i = 0, j = 0, m = 0; i < mid && j < size - mid; ) {
    if (sub_array1[i] < sub_array2[j]) {
      array[m++] = sub_array1[i++];
    } else {
      array[m++] = sub_array2[j++];
    }
  }
  while (i < mid) {
    array[m++] = sub_array1[i++];
  }
  while (j < size - mid) {
    array[m++] = sub_array2[j++];
  }
  free(sub_array1);
  free(sub_array2);
}

static void merge_sort_impl(int array[], int size) {
  if (size > 1) {
    int mid = size / 2;
    merge_sort_impl(&array[0], mid);
    merge_sort_impl(&array[mid], size - mid);
    merge(&array[0], mid, size);
  }
}

void merge_sort(array_t *array) {
  merge_sort_impl(array->data, array->size);
}

